package com.ting.test.algorithms.大厂刷题班;

/**
 * 有2N个司机，
 * 调度中心将所有司机平分给A,B两个区域
 * 第i个司机去A区域可得收入为income[0]
 * 第i个司机去B区域可得收入为income[1]
 * 返回所有的分配方案中，能够使得所有司机的收入最高的方案，最高是多少钱
 */
public class 所有司机获得最大收入问题 {
    public static void main(String[] args) {
        int N = 10;
        int[][] income = new int[2 * N][2];
        int money = process(income);
    }

    private static int process(int[][] income) {
        if (income == null) {
            return 0;
        }
        int N = income.length;

        return f(income, 0, N);
    }

    /**
     * 该函数表示 从第i个司机开始，能够获得的最大的收入
     *
     * @param income 收入数组
     * @param i      第i个司机
     * @param rest   A区域还能去的名额
     * @return
     */
    private static int f(int[][] income, int i, int rest) {
        if (i == income.length) {
            return 0;
            //如果所有的司机都遍历完了，恰好A 区域也分配完了，
        }
        //如果还有司机
        if (income.length - i == rest) {//如果剩下的司机正好等于rest，表明剩下的司机都应该去A区域
            //如果A区域分配完了，则剩下所有的人都去B区域
            return income[i][0] + f(income, i + 1, rest - 1);
        }

        if (rest == 0) {
            //如果A区域分配完了，则剩下所有的人都去B区域
            return income[i][1] + f(income, i + 1, rest);
        }

        int p1 = income[i][0] + f(income, i + 1, rest - 1);//当前司机去A区域
        int p2 = income[i][1] + f(income, i + 1, rest);//当前司机去B区域
        return Math.max(p1, p2);
    }


    /**
     * 该函数表示 从第i个司机开始，能够获得的最大的收入
     *
     * @param income 收入数组
     * @param i      第i个司机
     * @param rest   A区域还能去的名额
     * @param dp     缓存 dp[income.length+1][rest+1]
     * @return
     */
    private static int f2(int[][] income, int i, int rest, int[][] dp) {
        if (dp[i][rest] != -1) {
            return dp[i][rest];
        }
        if (i == income.length) {
            dp[i][rest] = 0;
            //如果所有的司机都遍历完了，恰好A 区域也分配完了，
        }
        //如果还有司机
        if (income.length - i == rest) {//如果剩下的司机正好等于rest，表明剩下的司机都应该去A区域
            //如果A区域分配完了，则剩下所有的人都去B区域
            dp[i][rest] = income[i][0] + f(income, i + 1, rest - 1);
        }

        if (rest == 0) {
            //如果A区域分配完了，则剩下所有的人都去B区域
            dp[i][rest] = income[i][1] + f(income, i + 1, rest);
        }

        int p1 = income[i][0] + f(income, i + 1, rest - 1);//当前司机去A区域
        int p2 = income[i][1] + f(income, i + 1, rest);//当前司机去B区域
        dp[i][rest] = Math.max(p1, p2);
        return dp[i][rest];
    }


    /**
     * 该函数表示 从第i个司机开始，能够获得的最大的收入
     *
     * @param income 收入数组
     * @param i      第i个司机
     * @param rest   A区域还能去的名额
     * @param dp     缓存 dp[income.length+1][rest+1]
     * @return
     */
    private static int f3(int[][] income, int i, int rest, int[][] dp) {
        //跟家basecase
        for (int index = 0; index < rest; index++) {
            dp[income.length][index] = 0;
        }
        if (dp[i][rest] != -1) {
            return dp[i][rest];
        }
        //如果还有司机
        if (income.length - i == rest) {//如果剩下的司机正好等于rest，表明剩下的司机都应该去A区域
            //如果A区域分配完了，则剩下所有的人都去B区域
            dp[i][rest] = income[i][0] + dp[i + 1][rest - 1];
        }
        if (rest == 0) {
            //如果A区域分配完了，则剩下所有的人都去B区域
            dp[i][rest] = income[i][1] + dp[i + 1][rest];
        }

        int p1 = income[i][0] + dp[i + 1][rest - 1];//当前司机去A区域
        int p2 = income[i][1] + dp[i + 1][rest];//当前司机去B区域
        dp[i][rest] = Math.max(p1, p2);
        return dp[i][rest];
    }
}
